这题真的是写到心态爆炸。。

一道边分治 + 虚树

前置知识

边分治

顾名思义，就是选择一条边，类似点分治对所有经过该边的路径进行处理，但与点分治不同的是，边分治可能会被菊花图卡到 $O (n^2)$，故此时需要重构树，将之变为度数不超过三的二叉树

树重构

通过建立新的虚点进行重构，但要满足加入的虚点不影响最后答案计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void rebuild (int root, int father) {
	int nf = 0;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		LL w = Link[i].w;
		if (v == father) continue;
		if (! nf) {
			Insert (root, v, w), Insert (v, root, w);
			nf = root;
		}
		else {
			int k = ++ m; // 虚点
			Insert (nf, k, 0), Insert (k, nf, 0);
			Insert (k, v, w), Insert (v, k, w);
			nf = k;
		}
		rebuild (v, root);
	}
}

求中心边

于点分治的求重心略有不同，但本质是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
int cet, mini; // 重心边
bool visit[MAXM << 3]= {false}; // 边是否已经被经过
void findc (int n, int root, int father) {
	subsize[root] = 1;
	for (int i = Head[root]; ~ i; i = Link[i].next) {
		int v = Link[i].to;
		if (visit[i >> 1] || v == father) continue;
		findc (n, v, root);
		subsize[root] += subsize[v];
		int maxpart = max (subsize[v], n - subsize[v]); // 注意此处
		if (maxpart < mini) { mini = maxpart; cet = i; }
	}
}

题解

现在开始边分治，分治到某一边 $E$，将相应点分为两个连通块 $A, B$

考虑原式，其中 $d_T(x)$ 表示在树 $T$ 中 $x$ 距根节点（或分治中心）的长度，对两点 $i \in A, j \in B$
$$
ans = \max \{d_{T_1}(i) + d_{T_1}(j) + dist_{T_2}(i, j) + dist_{T_3}(i, j)\}
$$
此时对 $A \cup B$ 建立虚树，在虚树上跑 $\text{DFS}$，设此时访问到虚树上点 $p$，则式子可变为
$$
\begin{aligned}
ans &= \max \{d_{T_1}(i) + d_{T_1}(j) + d_{T_2}(i) + d_{T_2}(j) - 2 \times d_{T_2}(p) + dist_{T_3}(i, j)\} \\
&= \max \{(d_{T_1} + d_{T_2})(i) + (d_{T_1} + d_{T_2})(j)- 2 \times d_{T_2}(p) + dist_{T_3}(i, j)\}
\end{aligned}
$$
这就相当于给 $T_3$ 的点 $i, j$ 分别赋上权值 $value_i = d_{T_1}(i) + d_{T_2}(i), value_j = d_{T_1}(j) + d_{T_2}(j)$，然后求 $T_3$ 上点 $i \in A, j \in B$ 的 $i, j$ 间边权和在加上 $i, j$ 点权的最大值即可求得答案，就是给 $T_3$ 上的点黑白染色，求白点到黑点的端点点权即边权和的最大值

那么此时发现边权 $w_i$ 都是正整数，说明它们满足直径合并的定理，即新直径必定由原来两条直径的端点产生，这样就可以直接求了，在 $T_2$ 上 $\text{dp}$ 时顺便合并 $T_3$ 的答案

这么直接做时 $O (n \log^2 n)$ 的，常数一大那就玩球

其实优化到 $O (n \log n)$ 也是很显然的，写个 $\text{RMQ}$ 的 $\text{LCA}$，并且在建虚树时不用 $\text{sort}$ 而是基数排序就好了

代码

357行（包含少量注释）。。都不知多久没有打代码打的这么带感过了。。

$\text{debug}$ 真的就够受了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;

const int INF = 0x7fffffff;

inline LL getnum () {
	LL num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int N;

//T3
LL val[MAXN]= {0};
struct Tree3 {
	struct LinkedForwardStar { int to, next; LL w; } ;
	LinkedForwardStar Link[MAXM << 1];
	int Head[MAXN], size;
	void Insert (int u, int v, LL w) {
		Link[++ size].to = v; Link[size].w = w;
		Link[size].next = Head[u]; Head[u] = size;
	}

	int dfn[MAXN], ord, cnt;
	int depth[MAXN], value[MAXN << 1], bel[MAXN << 1];
	LL d[MAXN];
	void DFS (int root, int father) {
		dfn[root] = ++ ord;
		value[ord] = depth[root], bel[ord] = root;
		for (int i = Head[root]; i; i = Link[i].next) {
			int v = Link[i].to;
			LL w = Link[i].w;
			if (v == father) continue;
			depth[v] = depth[root] + 1;
			d[v] = d[root] + w;
			DFS (v, root);
			value[++ ord] = depth[root];
			bel[ord] = root;
		}
	}
	pair<int, int> ST[MAXN << 1][23];
	void RMQ () {
		for (int i = 1; i <= ord; i ++) ST[i][0] = make_pair (value[i], bel[i]);
		for (int j = 1; j <= 20; j ++)
			for (int i = 1; i + (1 << j) - 1 <= ord; i ++)
				if (ST[i][j - 1].first < ST[i + (1 << (j - 1))][j - 1].first) ST[i][j] = ST[i][j - 1];
				else ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
	}
	inline int LCA (int l, int r) {
		int k = log2 (r - l + 1);
		if (ST[l][k].first < ST[r - (1 << k) + 1][k].first) return ST[l][k].second;
		else return ST[r - (1 << k) + 1][k].second;
	}
	inline LL dist (int x, int y) {
		if (dfn[x] > dfn[y]) swap (x, y);
		int lca = LCA (dfn[x], dfn[y]);
		return val[x] + val[y] + d[x] + d[y] - 2ll * d[lca];
	}
	void build () {
		for (int i = 1; i < N; i ++) {
			int u = getnum (), v = getnum ();
			LL w = getnum ();
			Insert (u, v, w), Insert (v, u, w);
		}
		ord = 0;
		DFS (1, 0); RMQ ();
	}
} ;
Tree3 T3;

struct diam {
	int x, y; LL d;
	diam (int fx = 0, int fy = 0, LL fd = 0) : x (fx), y (fy), d (fd) {}
} ;
diam f[MAXN][2];
inline LL query (diam A, diam B) {
	LL d1 = max (T3.dist (A.x, B.x), T3.dist (A.x, B.y));
	LL d2 = max (T3.dist (A.y, B.x), T3.dist (A.y, B.y));
	return max (d1, d2);
}
diam merge (diam A, diam B) {
	LL maxi; diam ret;
	ret = A.d > B.d ? diam (A.x, A.y, maxi = A.d) : diam (B.x, B.y, maxi = B.d);
	if (T3.dist (A.x, B.x) > maxi) { ret = diam (A.x, B.x, maxi = T3.dist (A.x, B.x)); }
	if (T3.dist (A.x, B.y) > maxi) { ret = diam (A.x, B.y, maxi = T3.dist (A.x, B.y)); }
	if (T3.dist (A.y, B.x) > maxi) { ret = diam (A.y, B.x, maxi = T3.dist (A.y, B.x)); }
	if (T3.dist (A.y, B.y) > maxi) { ret = diam (A.y, B.y, maxi = T3.dist (A.y, B.y)); }
	return ret;
}

LL ans = 0;
int dfn[MAXN]= {0};
bool comp (const int& a, const int& b) { return dfn[a] < dfn[b]; }
//T2
int dye[MAXN]= {0};
bool iskey[MAXN]= {0}, isdye[MAXN][2]= {0};
int a[MAXN]= {0};
struct Tree2 {
	struct LinkedForwardStar { int to, next; LL w; } ;
	LinkedForwardStar Link[MAXM << 1];
	int Head[MAXN], size;
	void Insert (int u, int v, LL w) {
		Link[++ size].to = v; Link[size].w = w;
		Link[size].next = Head[u]; Head[u] = size;
	}

	int ord;
	int depth[MAXN], value[MAXN << 1], bel[MAXN << 1];
	LL d[MAXN];
	void DFS (int root, int father) {
		dfn[root] = ++ ord;
		value[ord] = depth[root], bel[ord] = root;
		for (int i = Head[root]; i; i = Link[i].next) {
			int v = Link[i].to;
			LL w = Link[i].w;
			if (v == father) continue;
			depth[v] = depth[root] + 1;
			d[v] = d[root] + w;
			DFS (v, root);
			value[++ ord] = depth[root];
			bel[ord] = root;
		}
	}
	pair<int, int> ST[MAXN << 1][23];
	void RMQ () {
		for (int i = 1; i <= ord; i ++) ST[i][0] = make_pair (value[i], bel[i]);
		int MAX = log2 (ord) + 1;
		for (int j = 1; j <= MAX; j ++)
			for (int i = 1; i + (1 << j) - 1 <= ord; i ++)
				if (ST[i][j - 1].first < ST[i + (1 << (j - 1))][j - 1].first) ST[i][j] = ST[i][j - 1];
				else ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
	}
	inline int LCA (int x, int y) {
		if (dfn[x] > dfn[y]) swap (x, y);
		int l = dfn[x], r = dfn[y];
		int k = log2 (r - l + 1);
		if (ST[l][k].first < ST[r - (1 << k) + 1][k].first) return ST[l][k].second;
		return ST[r - (1 << k) + 1][k].second;
	}

	int stack[MAXN], top;
	void add (int x) {
		if (! top) { stack[++ top] = x; return ; }
		int lca = LCA (stack[top], x);
		while (top > 1 && depth[lca] < depth[stack[top - 1]]) {
			Insert (stack[top - 1], stack[top], 0); top --;
		}
		if (depth[lca] < depth[stack[top]]) { Insert (lca, stack[top], 0); top --; }
		if (! top || stack[top] != lca) stack[++ top] = lca;
		stack[++ top] = x;
	}
	void cstr (int l, int r) { // 虚树构建
		size = 0;
		top = 0; if (a[l] != 1) stack[++ top] = 1;
		for (int i = l; i <= r; i ++) { add (a[i]); val[a[i]] += d[a[i]]; iskey[a[i]] = true; }
		while (top > 1) { Insert (stack[top - 1], stack[top], 0); top --; }
	}
	bool vis[MAXN];
	void dp (int u) { // dp
		vis[u] = true;
		if (iskey[u]) {
			isdye[u][dye[u]] = true;
			f[u][dye[u]] = diam (u, u, 0);
		}
		for (int i = Head[u]; i; i = Link[i].next) {
			int v = Link[i].to;
			dp (v);
			if (isdye[u][0] && isdye[v][1]) ans = max (ans, query (f[u][0], f[v][1]) - 2ll * d[u]);
			if (isdye[u][1] && isdye[v][0]) ans = max (ans, query (f[u][1], f[v][0]) - 2ll * d[u]);
			if (isdye[v][0]) {
				if (! isdye[u][0]) f[u][0] = f[v][0];
				else f[u][0] = merge (f[u][0], f[v][0]);
				isdye[u][0] = true;
			}
			if (isdye[v][1]) {
				if (! isdye[u][1]) f[u][1] = f[v][1];
				else f[u][1] = merge (f[u][1], f[v][1]);
				isdye[u][1] = true;
			}
		}
	}
	void del (int u) {
		for (int i = Head[u]; i; i = Link[i].next) {
			int v = Link[i].to; del (v);
		}
		Head[u] = val[u] = dye[u] = 0; iskey[u] = isdye[u][0] = isdye[u][1] = false;
	}
	void build () {
		for (int i = 1; i < N; i ++) {
			int u = getnum (), v = getnum ();
			LL w = getnum ();
			Insert (u, v, w), Insert (v, u, w);
		}
		ord = 0;
		DFS (1, 0); RMQ ();
		size = 0; memset (Head, 0, sizeof (Head));
		for (int i = 1; i <= N; i ++) a[i] = i;
		sort (a + 1, a + N + 1, comp);
	}
} ;
Tree2 T2;

// T1
struct Tree1_ori {
	struct LinkedForwardStar { int to, next; LL w; } ;
	LinkedForwardStar Link[MAXM << 1];
	int Head[MAXN], size;
	void Insert (int u, int v, LL w) {
		Link[++ size].to = v; Link[size].w = w;
		Link[size].next = Head[u]; Head[u] = size;
	}
} ;
Tree1_ori T1;

struct LinkedForwardStar {
	int to;
	LL w;

	int next;
} ;

LinkedForwardStar Link[MAXM << 3];
int Head[MAXN << 2];
int size = - 1;

void Insert (int u, int v, LL w) {
	Link[++ size].to = v;
	Link[size].w = w;
	Link[size].next = Head[u];

	Head[u] = size;
}

int m;
void rebuild (int root, int father) {
	int nf = 0;
	for (int i = T1.Head[root]; i; i = T1.Link[i].next) {
		int v = T1.Link[i].to;
		LL w = T1.Link[i].w;
		if (v == father) continue;
		if (! nf) {
			Insert (root, v, w), Insert (v, root, w);
			nf = root;
		}
		else {
			int k = ++ m;
			Insert (nf, k, 0), Insert (k, nf, 0);
			Insert (k, v, w), Insert (v, k, w);
			nf = k;
		}
		rebuild (v, root);
	}
}
int subsize[MAXN << 2]= {0};
int cet, mini; // 重心边
bool visit[MAXM << 3]= {false}; // 边是否已经被经过
void findc (int n, int root, int father) {
	subsize[root] = 1;
	for (int i = Head[root]; ~ i; i = Link[i].next) {
		int v = Link[i].to;
		if (visit[i >> 1] || v == father) continue;
		findc (n, v, root);
		subsize[root] += subsize[v];
		int maxpart = max (subsize[v], n - subsize[v]);
		if (maxpart < mini) { mini = maxpart; cet = i; }
	}
}
void coll (int p, int root, int father, LL d) {
	if (root <= N) { dye[root] = p; val[root] = d; }
	for (int i = Head[root]; ~ i; i = Link[i].next) {
		int v = Link[i].to;
		LL w = Link[i].w;
		if (visit[i >> 1] || v == father) continue;
		coll (p, v, root, d + w);
	}
}
int tp[2][MAXN]= {0};
void divide (int u, int n, int l, int r) {
	if (l > r) return ;
	cet = - 1, mini = INF; findc (n, u, 0);
	if (cet == - 1) return ;
	visit[cet >> 1] = true;
	int x = Link[cet].to, y = Link[cet ^ 1].to;
	coll (0, x, y, Link[cet].w); coll (1, y, x, 0);
	T2.cstr (l, r); T2.dp (1);
	int cnt[2]= {0};
	for (int i = l; i <= r; i ++) tp[dye[a[i]]][++ cnt[dye[a[i]]]] = a[i];
	for (int i = l; i <= l + cnt[0] - 1; i ++) a[i] = tp[0][i - l + 1];
	for (int i = l + cnt[0]; i <= r; i ++) a[i] = tp[1][i - l - cnt[0] + 1];
	T2.del (1); int szr = n - subsize[x];
	divide (x, subsize[x], l, l + cnt[0] - 1);
	divide (y, szr, l + cnt[0], r);
}

int main () {
	N = getnum ();
	for (int i = 1; i < N; i ++) {
		int u = getnum (), v = getnum ();
		LL w = getnum ();
		T1.Insert (u, v, w), T1. Insert (v, u, w);
	}
	T2.build (); T3.build ();
	memset (Head, - 1, sizeof (Head));
	m = N; rebuild (1, 0);
	divide (1, m, 1, N);
	cout << ans << endl;

	return 0;
}

/*
5
1 2 2
1 3 0
1 4 1
4 5 7
1 2 0
2 3 1
2 4 1
2 5 3
1 5 2
2 3 8
3 4 5
4 5 1
*/